<!DOCTYPE html>
<html>

<head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<meta name="apple-mobile-web-app-capable" content="yes"/>
<title>C8 - Solution-23航C | pansis.io</title>
<link rel="shortcut icon" href="https://github.pansis.site/favicon.ico">
<link href="https://github.pansis.site/styles/main.css" rel="stylesheet">
<link href="//at.alicdn.com/t/c/font_1678829_b85ccgkdqkr.css" rel="stylesheet">
<link href="//cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet">
<link rel="alternate" type="application/rss+xml" title="pansis.io » Feed" href="https://github.pansis.site/atom.xml">
        <meta name="description" content="A 诚信承诺书



难度
考点




1
输出字符串



示例代码 1
#include &lt;stdio.h&gt;
char s[4][100] =
{
	&quot;I promise I won't cheat in the..." />
        <meta name="keywords" content="23航C" />
        <!-- OG -->
        <meta property="og:locale" content="zh_CN">
        <meta property="og:title" content="C8 - Solution-23航C" />
        <meta property="og:type" content="article" />
        <meta property="og:description" content="A 诚信承诺书



难度
考点




1
输出字符串



示例代码 1
#include &amp;lt;stdio.h&amp;gt;
char s[4][100] =
{
	&amp;quot;I promise I won&#39;t cheat in the...">
        <meta property="og:url" content="https://github.pansis.site/post/C8 - Solution-23航C/" />
        <meta property="og:site_name" content="pansis.io">
        <meta property="og:updated_time" content="2024-05-17">
        <meta property="og:image" content="" />
        <meta property="og:image:secure_url" content="">
        <meta property="og:image:alt" content="C8 - Solution-23航C">
        <!-- Twitter (post.ejs) -->
        <meta name="twitter:card" content="summary_large_image">
        <meta name="twitter:title" content="C8 - Solution-23航C">
        <meta name="twitter:description" content="A 诚信承诺书



难度
考点




1
输出字符串



示例代码 1
#include &amp;lt;stdio.h&amp;gt;
char s[4][100] =
{
	&amp;quot;I promise I won&#39;t cheat in the...">
        <!-- <meta name="twitter:site" content="@WBoy0609">
        <meta name="twitter:creator" content="@WBoy0609"> -->
        <meta name="twitter:image" content="">
</head>

<body>
    <div class="main animated">
        <div class="header animated fadeInDown">
    <div class="site_title_container">
        <div class="site_title">
            <a href="https://github.pansis.site">pansis.io</a>
        </div>
    </div>
    <div class="my_socials">
        
            
        
            
        
            
        
            
        
            
        
            
        
            
        
        <a href="https://github.pansis.site/atom.xml" title="rss" target="_blank"><i class="iconfont icon-rss"></i></a>
    </div>
</div>

    <div class="header_menu">
        
            
                <a href="/" class="menu">首页</a>
            
        
            
                <a href="/tag/GWAaV2nvk/" class="menu">程序设计课程</a>
            
        
            
                <a href="/tag/24hangc" class="menu">比赛</a>
            
        
            
                <a href="/tag/L7r9STb75/" class="menu">Python教程</a>
            
        
            
                <a href="/tags" class="menu">分类</a>
            
        
        <div class="gridea-search-div">
            <form id="gridea-search-form" action="https://github.pansis.site/search/">
                <input class="gridea-search-input" autocomplete="off" spellcheck="false" name="q"/>
            </form>
        </div>
    </div>

            <div class="autopagerize_page_element">
                <div class="content">
                    <div class="post_page">
                        <div class="post animated fadeInDown">
                            <div class="post_title post_detail_title">
                                <h2>
                                    C8 - Solution-23航C
                                </h2>
                                <span class="article-info">
                                    2024-05-17, 4840 words, 23 min read
                                </span>
                            </div>
                            <div class="post_content markdown">
                                <p class="md_block">
                                    <span class="md_line md_line_start md_line_end">
                                        <h2 id="a-诚信承诺书"><code>A</code> 诚信承诺书</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>输出字符串</td>
</tr>
</tbody>
</table>
<h3 id="示例代码-1">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
char s[4][100] =
{
	&quot;I promise I won't cheat in the exam.&quot;,
	&quot;Life cannot possibly bear splendid flowers from lies.&quot;,
	&quot;Where is there dignity unless there is honesty?&quot;,
	&quot;If one loses honesty, he(she) is going to lose everything.&quot;
};
int main()
{
	int n;
	while(~scanf(&quot;%d&quot;, &amp;n))	puts(s[n]);
	puts(s[0]);
	return 0;
}
</code></pre>
<h3 id="示例代码-2">示例代码 2</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	int n;
	while(~scanf(&quot;%d&quot;, &amp;n))
		switch(n)
		{
			case 1:
				puts(&quot;Life cannot possibly bear splendid flowers from lies.&quot;);
				break;
			case 2:
				puts(&quot;Where is there dignity unless there is honesty?&quot;);
				break;
			case 3:
				puts(&quot;If one loses honesty, he(she) is going to lose everything.&quot;);
				break;
		}
	puts(&quot;I promise I won't cheat in the exam.&quot;);
	return 0;
}
</code></pre>
<h2 id="b-计算数列"><code>B</code> 计算数列</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>浮点数运算</td>
</tr>
</tbody>
</table>
<h3 id="题目分析">题目分析</h3>
<p>按题目要求，迭代计算 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 次即可。</p>
<h3 id="示例代码-1-2">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	double x;
	int k;
	scanf(&quot;%lf %d&quot;, &amp;x, &amp;k);
	printf(&quot;%.3f&quot;, x);
	for(int i = 1; i &lt; k; ++i) // 循环k-1次
	{
		x = (4 * x - 2) / (x + 1); // 更新x的值
		printf(&quot; %.3f&quot;, x);
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-2">示例代码 2</h3>
<p>可以推导出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mfrac><mrow><msub><mi>a</mi><mi>n</mi></msub><mo>−</mo><mn>1</mn></mrow><mrow><msub><mi>a</mi><mi>n</mi></msub><mo>−</mo><mn>2</mn></mrow></mfrac><mo>=</mo><mfrac><mrow><msub><mi>a</mi><mn>1</mn></msub><mo>−</mo><mn>1</mn></mrow><mrow><msub><mi>a</mi><mn>1</mn></msub><mo>−</mo><mn>2</mn></mrow></mfrac><msup><mrow><mo fence="true">(</mo><mfrac><mn>3</mn><mn>2</mn></mfrac><mo fence="true">)</mo></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><annotation encoding="application/x-tex">\dfrac{a_n-1}{a_n-2} = \dfrac{a_1-1}{a_1-2}\left(\dfrac32\right)^{n-1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:2.1574400000000002em;vertical-align:-0.8360000000000001em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.32144em;"><span style="top:-2.3139999999999996em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">2</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.8360000000000001em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:2.604038em;vertical-align:-0.95003em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.32144em;"><span style="top:-2.3139999999999996em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">2</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.8360000000000001em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner"><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size3">(</span></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.32144em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord">2</span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord">3</span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size3">)</span></span></span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:1.6540080000000001em;"><span style="top:-3.9029000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">n</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span></span></span></span></span></span></span></span>，进而求出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>a</mi><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">a_n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>。</p>
<p>其实没有必要，仅作为数学拓展~</p>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	double x;
	int k;
	scanf(&quot;%lf%d&quot;, &amp;x, &amp;k);
	double y = (x - 1) / (x - 2), z = 1;
	for(int i = 0; i &lt; k; ++i, z *= 1.5)
		printf(&quot;%.3f &quot;, (2 * y * z - 1) / (y * z - 1));
	return 0;
}
</code></pre>
<h2 id="c-绘制靶心"><code>C</code> 绘制靶心</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>2</td>
<td>输出字符画</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-2">题目分析</h3>
<p>两种思路。</p>
<p>第一种较为简单，输出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>n</mi><mo>×</mo><mn>2</mn><mi>n</mi></mrow><annotation encoding="application/x-tex">2n\times 2n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mord mathdefault">n</span></span></span></span> 个字符，根据每个字符所在的位置判断应该输出什么字符。</p>
<p>第二种比较通用，输出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>n</mi></mrow><annotation encoding="application/x-tex">2n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mord mathdefault">n</span></span></span></span>​ 行字符串，每行输出每行的各部分。</p>
<p>具体见示例代码。</p>
<h3 id="示例代码-1-3">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	int n;
	scanf(&quot;%d&quot;, &amp;n);
	for (int i = 0; i &lt; 2 * n; i++)
	{
		for (int j = 0; j &lt; 2 * n; j++)
			if(i == j) putchar('\\');
			else if(i + j == 2 * n - 1) putchar('/');
			else putchar(' ');
		putchar('\n');
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-3">示例代码 2</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	int n;
	scanf(&quot;%d&quot;, &amp;n);
    // 输出前n行
	for(int i = 0; i &lt; n; ++i)
	{
		for(int j = 0; j &lt; i; ++j) putchar(' ');
		putchar('\\');
		for(int j = 1; j &lt; n - i; ++j) putchar(' ');
		for(int j = 1; j &lt; n - i; ++j) putchar(' ');
		putchar('/');
		for(int j = 0; j &lt; i; ++j) putchar(' ');
		printf(&quot;\n&quot;);
	}
    // 输出后n行
	for(int i = 0; i &lt; n; ++i)
	{
		for(int j = 1; j &lt; n - i; ++j) putchar(' ');
		putchar('/');
		for(int j = 0; j &lt; i; ++j) putchar(' ');
		for(int j = 0; j &lt; i; ++j) putchar(' ');
		putchar('\\');
		for(int j = 1; j &lt; n - i; ++j) putchar(' ');
		printf(&quot;\n&quot;);
	}	
	return 0;
}
</code></pre>
<h2 id="d-拾级而上"><code>D</code> 拾级而上</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>2</td>
<td>数据类型与范围，模运算性质</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-3">题目分析</h3>
<p>按照题意，需要对每组输入数据使用循环计算 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>a</mi><mtext> </mtext><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow><mtext> </mtext><mi>m</mi><mo separator="true">,</mo><msup><mi>a</mi><mn>2</mn></msup><mtext> </mtext><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow><mtext> </mtext><mi>m</mi><mo separator="true">,</mo><msup><mi>a</mi><mn>3</mn></msup><mtext> </mtext><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow><mtext> </mtext><mi>m</mi><mo separator="true">,</mo><mo>⋯</mo></mrow><annotation encoding="application/x-tex">a \bmod m, a^2 \bmod m, a^3 \bmod m, \cdots</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span><span class="mbin"><span class="mord"><span class="mord mathrm">m</span><span class="mord mathrm">o</span><span class="mord mathrm">d</span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span></span><span class="base"><span class="strut" style="height:1.008548em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span><span class="mbin"><span class="mord"><span class="mord mathrm">m</span><span class="mord mathrm">o</span><span class="mord mathrm">d</span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span></span><span class="base"><span class="strut" style="height:1.008548em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span><span class="mbin"><span class="mord"><span class="mord mathrm">m</span><span class="mord mathrm">o</span><span class="mord mathrm">d</span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">⋯</span></span></span></span> 的结果，直到找到结果为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 的情况，输出此时的指数值，即为答案。</p>
<p>注意到模数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">m</span></span></span></span> 可能的最大值为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span>，取模后的数相乘也有可能会超出 <code>int</code> 范围，因此需要使用 <code>long long</code> 类型变量存储中间结果。</p>
<h3 id="示例代码">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	int a, m;
	while (~scanf(&quot;%d%d&quot;, &amp;a, &amp;m))
	{
		long long p = 1;
		for (int i = 1; i &lt; m; ++i)
		{
			p = p * a % m;
			if (p == 1)
			{
				printf(&quot;%d\n&quot;, i);
				break;
			}
		}
	}
	return 0;
}
</code></pre>
<h2 id="e-剪刀-石头-布"><code>E</code> 剪刀 石头 布</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>3</td>
<td>条件 循环</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-4">题目分析</h3>
<p>本题需要根据每位玩家展示的物品进行分类讨论，分别包括</p>
<ul>
<li>三位玩家选择的物品都不相同（均不加分）</li>
<li>三位玩家选择的物品都相同（均不加分）</li>
<li>场上只出了 “剪刀” 和 “石头” （出“石头”的玩家加分）</li>
<li>场上只出了 “剪刀” 和 “布” （出“剪刀”的玩家加分）</li>
<li>场上只出了 “布” 和 “石头” （出“布”的玩家加分）</li>
</ul>
<h3 id="示例代码-1-4">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int score[3];
void add_score(int n, int sit[])
{
	for (int i = 0; i &lt; 3; ++i)
	{
		if (sit[i] == n)
			score[i]++;
	}
}
int main()
{
	int m;
	scanf(&quot;%d&quot;, &amp;m);  // 轮数
	int sit[3];
	for (int i = 0; i &lt; m; ++i)
	{
		int num[3] = {0}; // 用于记录剪刀石头布的出现次数
		for (int j = 0; j &lt; 3; ++j)
		{
			scanf(&quot;%d&quot;, &amp;sit[j]);
			num[sit[j]]++;
		}
		if (sit[0] == sit[1] &amp;&amp; sit[1] == sit[2]) // 如果三者出的一样，不加分
			continue;
		if (sit[0] != sit[1] &amp;&amp; sit[0] != sit[2] &amp;&amp; sit[1] != sit[2]) // 如果三者出的都一样，不加分
			continue;
		if (num[2] == 0) // 场上只出了 “剪刀” 和 “石头” ，则出“石头”1的玩家获胜
			add_score(1, sit);
		if (num[1] == 0) // 场上只出了 “剪刀” 和 “布” ，则出“剪刀”0的玩家获胜
			add_score(0, sit);
		if (num[0] == 0) // 场上只出了 “布” 和 “石头” ，则出“布”2的玩家获胜
			add_score(2, sit);
	}
	for (int i = 0; i &lt; 3; ++i)
		printf(&quot;%d &quot;, score[i]);
	return 0;
}
</code></pre>
<h3 id="示例代码-2-4">示例代码 2</h3>
<p>可以发现，当且仅当 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>a</mi><mo>+</mo><mi>b</mi><mo>+</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">a+b+c</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">a</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">b</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">c</span></span></span></span> 是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>3</mn></mrow><annotation encoding="application/x-tex">3</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">3</span></span></span></span> 的倍数的时候会产生平局。</p>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int m, A, B, C, a, b, c;
int main()
{
	scanf(&quot;%d&quot;, &amp;m);
	while (m--)
	{
		scanf(&quot;%d %d %d&quot;, &amp;a, &amp;b, &amp;c);
		if ((a + b + c) % 3) // 若不是平局
		{
			if (a == (b + 1) % 3 || a == (c + 1) % 3) // 若A获胜
				A++;
			if (b == (a + 1) % 3 || b == (c + 1) % 3) // 若B获胜
				B++;
			if (c == (a + 1) % 3 || c == (b + 1) % 3) // 若C获胜
				C++;
		}
	}
	printf(&quot;%d %d %d&quot;, A, B, C);
	return 0;
}
</code></pre>
<h2 id="f-奇妙的数列2024"><code>F</code> 奇妙的数列2024</h2>
<table>
<thead>
<tr>
<th style="text-align:center">难度</th>
<th style="text-align:center">知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">3</td>
<td style="text-align:center">二进制</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-5">题目分析</h3>
<p>给出了递归函数式，直接按照函数递归计算 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 的值是可以算出来的，单次时间复杂度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>log</mi><mo>⁡</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">\log n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">n</span></span></span></span>，但后面还要求 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 出现第一次的位置，这个问题用递归不好解决，枚举计算复杂度显然是不对的。</p>
<p>再仔细观察 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 的递推公式，可以发现其算法与十进制转二进制的方法（<strong>除二取余</strong>）类似，进而想到用二进制运算求解本题，推导出这里的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 表示 <strong><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">n</span></span></span></span> 的二进制表示中 <code>1</code> 出现的次数</strong>。</p>
<p>那么，既然明白了 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 的意义，就很方便求出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><msup><mi>n</mi><mo mathvariant="normal">′</mo></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n&#x27;)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.001892em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.751892em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span> 了：如果一个数的二进制的低 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 位全部是 <code>1</code>，其余位全部是 <code>0</code>，那它显然是值 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> 首次出现的位置。</p>
<h3 id="示例代码-2">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;

void solve() {
    long long x;
    scanf(&quot;%lld&quot;, &amp;x);
    long long cnt = 0, res = 0;
    for (int i = 62; i &gt;= 0; i--) // 统计x中1的个数
        cnt += x &gt;&gt; i &amp; 1;
    for (int i = 0; i &lt; cnt; i++)
        res = res &lt;&lt; 1 | 1;
    // 等价于 res = (1 &lt;&lt; cnt) - 1;
    printf(&quot;%lld %lld\n&quot;, cnt, res);
}

int main() {
    int T;
    scanf(&quot;%d&quot;, &amp;T);
    while (T--) {
        solve();
    }
    return 0;
}
</code></pre>
<h2 id="g-卓拉字典序"><code>G</code> 卓拉字典序</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4</td>
<td>二维数组排序，字符串</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-6">题目分析</h3>
<p>如果我们将卓拉语单词中的每一个字母，以字母表顺序从小到大替换为a~z，则可以直接使用 <code>strcmp</code> 进行字典序的比较了。比较完反替换并输出即可。</p>
<p>当然也可以直接自己写卓拉语的字符串比较函数。</p>
<h3 id="示例代码-1-5">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
int ord[28]; // 卓拉语中每个字母对应的a~z中字母
int reord[28]; // a~z中字母对应的卓拉语中的每个字母
char s[20005][105]; // 字符串数组
int cmp(const void *aa, const void *bb)  // 比较函数
{
	char *a = (char*)aa, *b = (char*)bb;
	return strcmp(a, b);
}
void trans(char *s)  // 卓拉语中每个字母转化成对应顺序的a~z中字母
{
	int len = (int)strlen(s);
	for (int i = 0; i &lt; len; i++)
	{
		s[i] = 'a' + ord[s[i] - 'a'];
	}
}
void retrans(char *s)  // a~z中字母转化回卓拉语中的每个字母
{
	int len = (int)strlen(s);
	for (int i = 0; i &lt; len; i++)
	{
		s[i] = 'a' + reord[s[i] - 'a'];
	}
}
int main()
{
	int n;
	scanf(&quot;%d&quot;, &amp;n);
	getchar();
	for (int i = 0; i &lt; 26; i++)
	{
		char c;
		scanf(&quot;%c&quot;, &amp;c);
		ord[c - 'a'] = i;
		reord[i] = c - 'a';
	}
	for (int i = 0; i &lt; n; i++)
	{
		scanf(&quot;%s&quot;, s[i]);
		trans(s[i]); // 输入并替换为对应的a~z
	}
	qsort(s, n, sizeof(s[0]), cmp);
	for (int i = 0; i &lt; n; i++)
	{
		retrans(s[i]); // 反替换并输出
		printf(&quot;%s\n&quot;, s[i]);
	}
    return 0;
}
</code></pre>
<h3 id="示例代码-2-5">示例代码 2</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
char s[20005][105], order[128]; // order[i]表示ascii码为i的字符的优先级，值越小优先级越高
int cmp(const void *p, const void *q)
{
	char *x = p, *y = q;
	while(*x &amp;&amp; *x == *y) x++, y++; // 找到字符串结尾或者两个字符串中第一个不同的字符
	return order[*x] - order[*y]; // 返回两个字符串第一个不同字符的优先级之差，均相同时返回值为0。
}
int main()
{
	int n;
	scanf(&quot;%d &quot;, &amp;n); // 空格跳过第一行末换行符
	for(int i = 1; i &lt;= 26; ++i) // 记录每个字符的优先级1~26
		order[getchar()] = i;
	// 注意'\0'的优先级最高，为0
	getchar(); // 吃掉行末换行符
	for(int i = 0; i &lt; n; ++i)
		gets(s[i]);
	qsort(s, n, sizeof(s[0]), cmp); // 排序
	for(int i = 0; i &lt; n; ++i)
		puts(s[i]);
	return 0;
}
</code></pre>
<h2 id="h-复数也有最大公约数"><code>H</code> 复数也有最大公约数！</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4</td>
<td>结构体，函数</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-7">题目分析</h3>
<p>用结构体实现复整数结构体，按照题目描述实现复数取模函数和最大公约数函数即可。</p>
<h3 id="示例代码-3">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;math.h&gt;
typedef struct
{
	long long r, i;
} Complex;
Complex mod(Complex a, Complex d)
{
	Complex b = // b = a / d（转为double计算，然后四舍五入）
	{
		round((double)(a.r * d.r + a.i * d.i) / (d.r * d.r + d.i * d.i)),
		round((double)(a.i * d.r - a.r * d.i) / (d.r * d.r + d.i * d.i))
	};
	Complex g = // g = a - b * d
	{
		a.r - (b.r * d.r - b.i * d.i),
		a.i - (b.r * d.i + b.i * d.r)
	};
	return g;
}
Complex gcd(Complex a, Complex b)
{
	return b.r == 0 &amp;&amp; b.i == 0 ? a : gcd(b, mod(a, b));
}
int main()
{
	Complex a, b;
	scanf(&quot;%lld%lldi%lld%lldi&quot;, &amp;a.r, &amp;a.i, &amp;b.r, &amp;b.i); // 读入
	Complex d = gcd(a, b); // 求gcd(a,b)
	// 保证d实部为正，虚部非负
	if(d.r &lt;= 0)
	{
		d.r = -d.r;
		d.i = -d.i;
	}
	if(d.i &lt; 0)
	{
		long long t = d.r;
		d.r = -d.i;
		d.i = t;
	}
	// 输出
	printf(&quot;%lld%+lldi&quot;, d.r, d.i);
	return 0;
}
</code></pre>
<h2 id="i-点燃草地"><code>I</code> 点燃草地</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4~5</td>
<td>二维数组</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-8">题目分析</h3>
<p>本题有两种思路：</p>
<ol>
<li>
<p>直接使用二维数组进行模拟</p>
<p>使用二维数组标记每一时刻被点燃的草地，再循环每一时刻并遍历每个位置，根据上一时刻的状态进行更新。</p>
</li>
<li>
<p>递归</p>
<p>从初始被点燃的草地开始，递归地搜索周围的草地，并根据题目中的点燃条件更新周围草地的状态并继续进行递归。</p>
</li>
</ol>
<p>建议结合代码和注释进行理解</p>
<h3 id="示例代码-1-直接模拟">示例代码 1 直接模拟</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;

int a[105][105]; // 燃点
int fire[105][105]; // 标记点燃位置
int temp_fire[105][105]; // 临时存储数组
int judge(int i, int j){ // 判断当前位置的草地是否满足点燃条件
    return ((fire[i - 1][j] &amp;&amp; a[i - 1][j] &gt;= a[i][j])
    || (fire[i + 1][j] &amp;&amp; a[i + 1][j] &gt;= a[i][j])
    || (fire[i][j - 1] &amp;&amp; a[i][j - 1] &gt;= a[i][j])
    || (fire[i][j + 1] &amp;&amp; a[i][j + 1] &gt;= a[i][j]));
}
int main(){
    int n;
    scanf(&quot;%d&quot;, &amp;n);
    int x, y;
    scanf(&quot;%d %d&quot;, &amp;x, &amp;y);
    for (int i = 1; i &lt;= n; i++) { // 输入
        for (int j = 1; j &lt;= n; j++) {
            scanf(&quot;%d&quot;, &amp;a[i][j]);
        }
    }
    fire[x][y] = 1; // 初始化
    temp_fire[x][y] = 1; // 初始化
    int flag = 1; // 标记该次循环是否点燃过草地
    while (flag) { // 该次循环没有点燃过草地时跳出
        flag = 0;
        for (int i = 1; i &lt;= n; i++) {
            for (int j = 1; j &lt;= n; j++) {
               // 若当前草地已经被点燃，保持点燃状态
                if (!fire[i][j]) { // 当前草地未被点燃，需要判断是否需要点燃
                    temp_fire[i][j] = judge(i, j);
                    flag = judge(i, j) | flag; // 更新点燃标记
                }
            }
        }
        for (int i = 1; i &lt;= n; i++) {
            for (int j = 1; j &lt;= n; j++) {
                fire[i][j] = temp_fire[i][j]; // 整体拷贝
            }
        }
      // 注意，本题可以在不使用临时存储数组的情况下得到正确答案，但这种情况下fire数组的更新过程就不是时序的了，鉴于时序更新的方法更好理解，题解采用在临时存储数组上更新并整体拷贝的方法
    }
    for (int i = 1; i &lt;= n; i++) { // 输出
        for (int j = 1; j &lt;= n; j++) {
            printf(&quot;%d&quot;, fire[i][j]);
        }
        printf(&quot;\n&quot;);
    }
    return 0;
}
</code></pre>
<h3 id="示例代码-2-递归">示例代码 2 递归</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;

int a[105][105];
int fire[105][105];
int isFind[105][105]; // 重复访问
int n;
void dfs(int x, int y){
    if (!(1 &lt;= x &amp;&amp; x &lt;= n &amp;&amp; 1 &lt;= y &amp;&amp; y &lt;= n)) { // 越界
        return;
    }
    if (!fire[x][y]) { // 不需要递归未被点燃的草地
        return;
    }
    if (isFind[x][y]) { // 重复遍历直接跳回
        return;
    }
    isFind[x][y] = 1; // 标记
    fire[x - 1][y] = (fire[x - 1][y] || a[x - 1][y] &lt;= a[x][y]); // 更新四周草地状态
    dfs(x - 1, y); // 递归
    fire[x + 1][y] = (fire[x + 1][y] || a[x + 1][y] &lt;= a[x][y]);
    dfs(x + 1, y);
    fire[x][y - 1] = (fire[x][y - 1] || a[x][y - 1] &lt;= a[x][y]);
    dfs(x, y - 1);
    fire[x][y + 1] = (fire[x][y + 1] || a[x][y + 1] &lt;= a[x][y]);
    dfs(x, y + 1);
}
int main(){
    scanf(&quot;%d&quot;, &amp;n);
    int x, y;
    scanf(&quot;%d %d&quot;, &amp;x, &amp;y);
    for (int i = 1; i &lt;= n; i++) { // 输入
        for (int j = 1; j &lt;= n; j++) {
            scanf(&quot;%d&quot;, &amp;a[i][j]);
        }
    }
    fire[x][y] = 1; // 点燃初始位置
    dfs(x, y);
    for (int i = 1; i &lt;= n; i++) { // 输出
        for (int j = 1; j &lt;= n; j++) {
            printf(&quot;%d&quot;, fire[i][j]);
        }
        printf(&quot;\n&quot;);
    }
    return 0;
}
</code></pre>
<p>当然，这道题还有很多更为简洁的写法，题解中只展示了较好理解的两种写法，欢迎大家自己尝试解决本题时写出更优雅简洁的代码～</p>
<p><em>Author: SiSi &amp; Miss Firefly</em></p>
<blockquote>
<p><em>短短三月的C语言学习之旅如梦般短暂</em></p>
<p><em>SiSi 和 Firefly 小姐在此祝愿大家都能有所收获，取得满意的成绩～</em></p>
<p><em>愿我们在清醒的现实中再会</em></p>
</blockquote>
<h2 id="j-贤者之石"><code>J</code> 贤者之石</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>5</td>
<td>前缀和</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-9">题目分析</h3>
<p>由题意，我们需要找到一个连续子串，使得其中 <code>R</code> 和 <code>B</code> 的数量相同。</p>
<p>考虑枚举每一个字符，再枚举以该字符为头的字符串，时间复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span>。注意到数据范围 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">∣</mi><mtext mathvariant="monospace">s</mtext><mi mathvariant="normal">∣</mi><mo>≤</mo><mn>2</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">|\texttt{s}| \leq 2 \times 10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord text"><span class="mord texttt">s</span></span><span class="mord">∣</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span>，无法通过本题。</p>
<p>记 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mtext mathvariant="monospace">s</mtext><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">\texttt{s}_{ij}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.716668em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord text"><span class="mord texttt">s</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span></span> 为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mtext mathvariant="monospace">s</mtext></mrow><annotation encoding="application/x-tex">\texttt{s}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord text"><span class="mord texttt">s</span></span></span></span></span> 从第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 个字符到第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 个字符的连续子串。为了简化状态的表示，我们用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">−</span><span class="mord">1</span></span></span></span> 来表示 <code>R</code> 和 <code>B</code>，并记第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 个字符的数值为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">a_i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>。当子串 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mtext mathvariant="monospace">s</mtext><mrow><mi>i</mi><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">\texttt{s}_{ij}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.716668em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord text"><span class="mord texttt">s</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span></span> 满足题意时，有：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mi>i</mi></mrow><mi>j</mi></munderover><msub><mi>a</mi><mi>k</mi></msub><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">\sum_{k=i}^{j}a_k=0
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:3.16089em;vertical-align:-1.302113em;"></span><span class="mop op-limits"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.8587770000000001em;"><span style="top:-1.8478869999999998em;margin-left:0em;"><span class="pstrut" style="height:3.05em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span><span class="mrel mtight">=</span><span class="mord mathdefault mtight">i</span></span></span></span><span style="top:-3.0500049999999996em;"><span class="pstrut" style="height:3.05em;"></span><span><span class="mop op-symbol large-op">∑</span></span></span><span style="top:-4.347113em;margin-left:0em;"><span class="pstrut" style="height:3.05em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.302113em;"><span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.33610799999999996em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span></span></p>
<p>记 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">S_n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>{</mo><msub><mi>a</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">\{a_n\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">}</span></span></span></span> 的前 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">n</span></span></span></span> 项和，则有：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>j</mi></msub><mo>−</mo><msub><mi>S</mi><mi>i</mi></msub><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">S_j-S_i=0
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span></span></p>
<p>因此我们可以计算出 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>{</mo><msub><mi>S</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">\{S_n\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">}</span></span></span></span>，求该数列中相同项的项数之差最大值。考虑用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi><mi>o</mi><msub><mi>s</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">pos_k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.33610799999999996em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 表示 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">S_n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 的值为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 出现的最早位置。由于数组下标为非负数，我们将 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>n</mi></msub></mrow><annotation encoding="application/x-tex">S_n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 整体加上 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">∣</mi><mtext mathvariant="monospace">s</mtext><msub><mi mathvariant="normal">∣</mi><mrow><mi>m</mi><mi>a</mi><mi>x</mi></mrow></msub></mrow><annotation encoding="application/x-tex">|\texttt{s}|_{max}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord text"><span class="mord texttt">s</span></span><span class="mord"><span class="mord">∣</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">m</span><span class="mord mathdefault mtight">a</span><span class="mord mathdefault mtight">x</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>，即 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">2 \times 10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span>。因为一次遍历即可同时更新 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">S_k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.33610799999999996em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi><mi>o</mi><msub><mi>s</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">pos_k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.33610799999999996em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 的值，因此不需要为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>{</mo><msub><mi>S</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">\{S_n\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.05764em;">S</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:-0.05764em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">}</span></span></span></span> 申请一个数组，用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mi>u</mi><mi>m</mi></mrow><annotation encoding="application/x-tex">sum</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span><span class="mord mathdefault">u</span><span class="mord mathdefault">m</span></span></span></span> 表示即可。</p>
<h3 id="示例代码-4">示例代码</h3>
<pre><code class="language-C">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#define N 200000
#define MAX(a, b) ((a) &lt; (b) ? (b) : (a))

int sum = N, i, pos[2 * N + 5], ans;
char s[N + 5];

int main()
{
	scanf(&quot;%s&quot;, s);
	for (i = 1; s[i - 1]; i++)
	{
		sum += s[i - 1] == 'R' ? 1 : -1;
		if (sum != N &amp;&amp; !pos[sum]) // 为什么？
			pos[sum] = i;
		else
			ans = MAX(ans, i - pos[sum]);
	}
	printf(&quot;%d&quot;, ans);
	return 0;
}
</code></pre>
<p>当 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi><mi>o</mi><msub><mi>s</mi><mi>k</mi></msub><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">pos_k=0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.33610799999999996em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span> 时，表示数值 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 还未出现过，因此可以更新。但有一个例外，不能更新 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi><mi>o</mi><msub><mi>s</mi><mi>N</mi></msub></mrow><annotation encoding="application/x-tex">pos_N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.32833099999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.10903em;">N</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 的值，因为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>p</mi><mi>o</mi><msub><mi>s</mi><mi>N</mi></msub></mrow><annotation encoding="application/x-tex">pos_N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">p</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.32833099999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.10903em;">N</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 显然一定为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span>，而 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi><mi>u</mi><mi>m</mi><mo>=</mo><mi>N</mi></mrow><annotation encoding="application/x-tex">sum=N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span><span class="mord mathdefault">u</span><span class="mord mathdefault">m</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">N</span></span></span></span> 表示此时的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mtext mathvariant="monospace">s</mtext><mrow><mn>1</mn><mi>i</mi></mrow></msub></mrow><annotation encoding="application/x-tex">\texttt{s}_{1i}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord text"><span class="mord texttt">s</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 是满足题意的子串。</p>
<h2 id="k-qaq"><code>K</code> qaq</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>6</td>
<td>贪心</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-10">题目分析</h3>
<p>可以证明，将 'q' 加在序列的两端，'a' 加在所有 'q' 的位置的中间，一定能使 &quot;qaq&quot; 子串最多。</p>
<h4 id="思路一">思路一：</h4>
<p>枚举加 'q' 的个数，逐个加入 'q'。如果当前子序列 &quot;aq&quot; 的个数大于 &quot;qa&quot; 的个数，那么这个 'q' 应该加到前面，否则应该加到后面。每次加 'q' 后维护子序列个数并更新答案。复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>+</mo><mi>x</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n+x)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">x</span><span class="mclose">)</span></span></span></span>​。</p>
<p>具体而言，首先求出初始字符串中 'q', 'a', &quot;qa&quot;, &quot;aq&quot;, &quot;qaq&quot; 的数量，每读入一个新字符，更新变量即可，循环遍历一遍即可求得。</p>
<p>然后计算只加入若干个 'q' 的情况。枚举加入 'q' 的个数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn><mo separator="true">,</mo><mn>1</mn><mo separator="true">,</mo><mo>⋯</mo><mtext> </mtext><mo separator="true">,</mo><mi>x</mi></mrow><annotation encoding="application/x-tex">0,1,\cdots,x</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">⋯</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">x</span></span></span></span>，若当前子序列 &quot;aq&quot; 的个数大于 &quot;qa&quot; 的个数，那么这个 'q' 应该加到前面，否则应该加到后面。更新维护 'q', &quot;qa&quot;, &quot;aq&quot;, &quot;qaq&quot; 的数量。</p>
<p>当新加入 'q' 的个数为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 的时候，还要加入 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>−</mo><mi>i</mi></mrow><annotation encoding="application/x-tex">x-i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 个 'a'，这 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>−</mo><mi>i</mi></mrow><annotation encoding="application/x-tex">x-i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 个 'a' 加在所有 'q' 的位置的中间，其对答案的贡献为 $\lfloor \frac q2 \rfloor (x-i) \lceil \frac q2 \rceil $。</p>
<p>最终答案为“只加入 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 个 'q' 的最大 &quot;qaq&quot; 个数”加上“$\lfloor \frac q2 \rfloor (x-i) \lceil \frac q2 \rceil $”的最大值。</p>
<h4 id="思路二">思路二：</h4>
<p>当加入 'q' 的数量确定时，子序列的个数是关于“加在前面的 'q' 的个数”的单峰函数。而最终答案是关于“加入 'q' 的数量”的单峰函数。可以利用三分/二次函数求极值的方法在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>x</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n \log x)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">x</span><span class="mclose">)</span></span></span></span> 或者 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>+</mo><mi>x</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n+x)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">x</span><span class="mclose">)</span></span></span></span> 或者 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span>​ 的时间通过。</p>
<h3 id="示例代码思路一">示例代码：思路一</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#define max(a, b) ((a) &gt; (b) ? (a) : (b))
long long n, x, q, a, qa, aq, qaq, ans;
int main()
{
	scanf(&quot;%lld%lld &quot;, &amp;n, &amp;x); // 注意这里读掉第一行末的换行符
	for(int i = 0; i &lt; n; ++i) // 循环统计初始字符串中 'q', 'a', &quot;qa&quot;, &quot;aq&quot;, &quot;qaq&quot; 的数量
	{
		if(getchar() == 'a') // 若初始字符串中第i个字符为 'a'
		{
			a++;
			qa += q;
		}
		else                 // 若初始字符串中第i个字符为 'a'
		{
			q++;
			aq += a;
			qaq += qa;
		}
	}
	for(int i = 0; i &lt;= x; ++i) // 枚举加入q的数量
	{
		// 计算答案，更新最大值
		ans = max(ans, qaq + (q + 1) / 2 * (q / 2) * (x - i)); // 注意此处运算顺序，要保证(q/2),((q+1)/2)向下取整
		// 加入'q'
		q++;
		if(aq &gt; qa) // 'q'加到最前面
		{
			qa += a;
			qaq += aq;
		}
		else        // 'q'加到最后面
		{
			aq += a;
			qaq += qa;
		}
	}
	printf(&quot;%lld&quot;, ans);
	return 0;
}
</code></pre>
<h3 id="ps">P.S.</h3>
<p>本题为 BCPC 2022（第十七届“快手杯”北京航空航天大学程序设计竞赛）决赛 F 题。</p>
<p>BCPC 北京航空航天大学程序设计竞赛每年吸引全校数百名程序爱好者参加，为广大程序设计爱好者搭建了一个学习、交流、竞技的平台。</p>
<p>欢迎感兴趣的同学积极关注参与！</p>
<h1 id="-end-">- End -</h1>
<br />
                                            
                                </p>
                            </div>
                            <div class="post_footer">
                                
                                    <div class="meta">
                                        <div class="info"><span class="field tags"><i class="iconfont icon-tag-sm"></i>
                                                
                                                    <a href="https://github.pansis.site/tag/24hc/" class="article-info">
                                                        23航C
                                                    </a>
                                                    
                                            </span>
                                        </div>
                                    </div>
                                    
                                        
                            </div>
                        </div>
                        
                            
                                <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
<div id="gitalk-container" style="padding-bottom: 20px;"></div>
<script>
    var pageId = (location.pathname).substring(1, 49) // Ensure uniqueness and length less than 50
    pageId = pageId.endsWith('/') ? pageId.slice(0, -1) : pageId // 以斜杠结尾则去除
    var gitalk = new Gitalk({
        clientID: '9d5eba33618472c44a07',
        clientSecret: '065a85ed04333ceebfc4f01d7ca1674175730339',
        repo: 'fzxl2003.github.io',
        owner: 'fzxl2003',
        admin: ['fzxl2003'],
        id: pageId,
        distractionFreeMode: false  // Facebook-like distraction free mode
    })
    gitalk.render('gitalk-container')
</script>
                                    
                                        
                                                    
                    </div>
                </div>
            </div>
    </div>
    <div class="footer">
    
    <div class="powered_by">
        <a href="https://codeberg.org/kytrun/gridea-theme-one" target="_blank">Theme One,</a>
        <a href="https://open.gridea.dev/" target="_blank">Powered by Gridea&#65281;</a>
    </div>
    
    
        <div class="footer_slogan">
            Powered by <a href="https://github.com/getgridea/gridea" target="_blank">Gridea</a>
        </div>
    
    <div id="back_to_top" class="back_to_top">
        <span>△</span>
    </div>
    
</div>

<script src="https://github.pansis.site/media/scripts/util.js"></script>
        <link rel="stylesheet" href="//unpkg.com/@highlightjs/cdn-assets@11.5.1/styles/default.min.css">
        <script src="//unpkg.com/@highlightjs/cdn-assets@11.5.1/highlight.min.js"></script>
        <script>hljs.highlightAll();</script>
</body>

</html>